package ArrayAndString;

public class String_3 {
    /**
     * 最长回文子串
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     * 示例 1：
     * <p>
     * 输入：s = "babad"
     * 输出："bab"
     * 解释："aba" 同样是符合题意的答案。
     * 示例 2：
     * <p>
     * 输入：s = "cbbd"
     * 输出："bb"
     * 示例 3：
     * <p>
     * 输入：s = "a"
     * 输出："a"
     * 示例 4：
     * <p>
     * 输入：s = "ac"
     * 输出："a"
     */
    //暴力解法 时间复杂度n3
    public static String longestPalindrome(String s) {
        int length = s.length();
        //最大回文字符串的长度
        int max = 0;
        String ans = "";
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length + 1; j++) {
                String substring = s.substring(i, j);
                //判断是否是回文，且当前的subString是否大于最大的回文字符串的长度
                if (isPalindRome(substring) && substring.length() > max) {
                    max = substring.length();
                    ans = substring;
                }
            }
        }
        return ans;
    }
    //判断字符串是否是回文字符串
    private static boolean isPalindRome(String substring) {
        int length = substring.length();
        for (int i = 0; i < length / 2; i++) {
            if (substring.charAt(i) != substring.charAt(length - i - 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String str = "babad";
        System.out.println(longestPalindrome(str));
    }
}
